package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 在排序数组中查找数字
 *
 * @author yuhushuan
 * @date 2020/6/29 14:24
 */
public class _53_1_NumberOfK {
    private static int getFirstK(int[] data, int k, int start, int end) {
        if (data == null || data.length == 0 || start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = data[middleIndex];

        if (middleData == k) {
            if ((middleIndex > 0 && data[middleIndex - 1] < k)
                    || middleIndex == 0) {
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        } else if (middleData > k) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getFirstK(data, k, start, end);
    }

    private static int getLastK(int[] data, int k, int start, int end) {
        if (data == null || data.length == 0 || start > end) {
            return -1;
        }
        int middleIndex = (start + end) >> 1;
        int middleData = data[middleIndex];

        if (middleData == k) {
            if ((middleIndex < data.length - 1 && data[middleIndex + 1] > k)
                    || middleIndex == data.length - 1) {
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        } else if (middleData > k) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getLastK(data, k, start, end);
    }

    private static int getNumberOfK(int[] data, int k) {
        if (data == null || data.length == 0) {
            return -1;
        }
        int first = getFirstK(data, k, 0, data.length - 1);
        int last = getLastK(data, k, 0, data.length - 1);

        int number = 0;
        if (first > -1 && last > -1) {
            number = last - first + 1;
        }
        return number;
    }

    public static void main(String[] args) {
        // 功能测试
        // 包含要查找的数字
        print(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 3);
        // 没有要查找的数字
        print(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 6);
        // 要查找的数字出现一次或多次
        print(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 4);

        // 边界值测试
        // 最大值
        print(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 5);
        //最小值
        print(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 1);
        // 只有一个数字
        print(new int[]{4}, 4);

        // 特殊输入测试
        print(null, 1);

    }

    private static void print(int[] data, int k) {
        System.out.println("数组：" + Arrays.toString(data));
        System.out.println("数值为：" + k + " 的个数为：" + getNumberOfK(data, k));
        System.out.println();
    }
}
